package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode005 
* @author      : ganwei 
* @date        : 2020年5月4日 
* @Description : TODO 
*/
public class Leetcode0005 {
	/**
	 * -解题思路，动态规划求解
	 */
    public String longestPalindrome(String s) {
    	int len = s.length();
    	/**
    	 * -1.如果字符串为一个字符，则返回
    	 */
    	if(len < 2) {
    		return s;
    	}
    	
    	/**
    	 * -2.初始化动态规划数组
    	 */
    	boolean dp[][] = new boolean[len][len];
    	for(int i = 0; i < len; i++) {
    		dp[i][i] = true;
    	}
    	/**
    	 * -3.1个字符的字符串一定为回文
    	 */
    	int maxLen = 1;
    	int start = 0;
    	
    	
    	/**
    	 * -4.循环逐层计算
    	 */
    	for(int j = 1; j < len; j++) {
    		for(int i = 0; i < j; i++) {
    			if(s.charAt(i) == s.charAt(j)) {
    				if(j - i < 3) {
        				dp[i][j] = true;
        			}else {
        				dp[i][j] = dp[i+1][j-1];
        			}
    			}
                if (dp[i][j]) {
                    int curLen = j - i + 1;
                    if (curLen > maxLen) {
                        maxLen = curLen;
                        start = i;
                    }
                }
    		}
    	}
    	
    	return s.substring(start, start+maxLen);
        
    }
	public static void main(String[] args) {
		Leetcode0005 l005 = new Leetcode0005();
		System.out.println(l005.longestPalindrome("babad"));
	}
}
